package everydayone.hasGroupsSize;

import java.util.HashMap;
import java.util.Map;

/**
 * @Date 2020/03/27
 * @author 王光浩
 * @Thinking 获取所有元素出现次数的最大公约数，如果最大公约数为1，返回false，否则返回true。
 * @Analysis 时间复杂度O（Nlogc），每两个数之间需要求最大公约数，然后一共需要求N次。空间复杂度O（N）
 */
public class MyMethodTwo {
	public boolean hasGroupsSizeX(int[] deck) {
		int g=0;  //保存所有元素的最大公约数
		//统计所有元素的出现次数
		HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
		for(int tem:deck)map.put(tem,map.getOrDefault(tem, 0)+1);
		for(Map.Entry<Integer,Integer> entry:map.entrySet()) {
			if(g==0) {
				g=entry.getValue();
			}
			else {
				g=gbc(g,entry.getValue());
			}
		}
		return g>=2;
    }
	private int gbc(int first,int second) {
		return second==0?first:gbc(second,first%second);				
	}
}
